package com.zj.study;

public class 最短路径问题Dijkstra {

    private static final int MAX = 99;
    private static final int START = 0;


    public static void main(String[] args) {
        System.out.println(3 > 1 + 4);
        int[][] arr = {
                {0, 4, 6, 6, MAX, MAX, MAX},
                {MAX, 0, 1, MAX, 2, MAX, MAX},
                {MAX, MAX, 0, MAX, 6, 4, MAX},
                {MAX, MAX, 2, 0, MAX, 5, MAX},
                {MAX, MAX, MAX, MAX, 0, MAX, 6},
                {MAX, MAX, MAX, MAX, 1, 0, 8},
                {MAX, MAX, MAX, MAX, MAX, MAX, MAX}
        };
//        int[][] arr={
//                {0,MAX,MAX,MAX},
//                {1,0,1,MAX},
//                {MAX,MAX,0,1},
//                {MAX,MAX,MAX,0}
//
//        };

        for (int i = 0; i < arr.length; i++) {
            int[] visited = new int[arr.length];
            visited[i] = 1;
            processShortest(arr, i, visited);

        }


        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + "\t\t\t\t");
            }
            System.out.println();
        }

    }

    public static void processShortest(int[][] arr, int start, int[] visited) {
        for (int k = 0; k < visited.length - 1; k++) {//注意通过for循环控制次数，比递归要清晰点。
            int index = getShortestIndex(arr, start, visited);
            if (index == -1) {
                return;
            }
            visited[index] = 1;

            for (int i = 0; i < arr.length; i++) {
                if (visited[i] != 1 && arr[start][i] > arr[start][index] + arr[index][i]) {//此处的visited[i]!=1很重要，只更新未被访问的点。
                    arr[start][i] = arr[start][index] + arr[index][i];
                }
            }
        }


    }

    public static int getShortestIndex(int[][] arr, int start, int[] visited) {
        int min = MAX;
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (visited[i] != 1 && arr[start][i] < min) {
                min = arr[start][i];
                index = i;
            }
        }
        System.out.println(start + "----" + index);
        return index;
    }
}
